package com.atguigu.recursion;

/*
递归求解迷宫问题
 */
public class MiGong {
    public static void main(String[] args) {
        int[][] arr = new int[8][7];
        for (int i=0;i<7;i++){
            arr[0][i]=1;
            arr[7][i]=1;
        }
        for (int i=0;i<8;i++){
            arr[i][0]=1;
            arr[i][6]=1;
        }

        arr[3][1] = 1;
        arr[3][2] = 1;

        //从1，1点开始执行
        findWay(arr,1,1);

        for (int i=0;i<8;i++){
            for (int j=0;j<7;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }

    //定义墙为1，路为2，路走不通为3
    //定义走路方式，先向下，不通再向右，不通再向左，不通再向上
    public static boolean findWay(int arr[][],int i,int j){
        if (arr[6][5]==2){
            return true;
        }
        if(arr[i][j]==1){
            return false;
        }
        arr[i][j]=2;
        if (findWay(arr,i+1,j)){
            return true;
        }else if (findWay(arr,i,j+1)){
            return true;
        }else if (findWay(arr,i,j-1)){
            return true;
        }else if (findWay(arr,i-1,j)){
            return true;
        }else {
            arr[i][j]=3;
            return false;
        }


    }
}
